package argo.hot100.greedy;

import java.util.*;

public class PartitionLabels {

    public List<Integer> partitionLabels(String s) {

        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        int[] maxIndex = new int[26];

        for (int i = 0; i < s.length(); i++) {
            maxIndex[s.charAt(i) - 'a'] = i;
        }

        int start = 0;
        int end = 0;

        for (int i = 0; i < s.length(); i++) {
            end = Math.max(maxIndex[s.charAt(i) - 'a'], end);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }

        return res;
    }


    public List<Integer> partitionLabelsOld(String s) {

        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return res;
        }
        Map<Character, Integer> maxIndexMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            maxIndexMap.put(s.charAt(i), i);
        }

        res.add(1);
        Integer curMaxIndex = 0;
        Integer lastIndex = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);


            if (i > curMaxIndex && !set.contains(c)) {
                res.add(i - lastIndex);
                lastIndex = i;
                System.out.println(i);
            }
            set.add(c);
            curMaxIndex = Math.max(maxIndexMap.get(c), curMaxIndex);

            //last index process
            if (curMaxIndex == s.length() - 1) {
                res.add(s.length() - lastIndex);
                System.out.println(i);
                break;
            }
        }
        res.remove(0);
        return res;
    }
}
